/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package dramsy_christian_bellamn_floyd;

/**
 * CLasse pour l'algorithme de Bellman
 * @author <a href="mailto:christian.dramsy@gmail.com">DRAMSY Christian</a>
 */
public class Bellman {

    private Graphe graphe;

    /**
     * Affichele resultat de l'algorithme de Bellman
     * @param distance
     * @param antecedant
     * @param beginNode
     */
    private void displayResult(int[] distance, int[] antecedant, int beginNode) {
        int pred = -1;
        for (int i = 0; i < distance.length; i++) {
            if (i != beginNode) {
                System.out.println("------------------------------------------------------------------------");
                System.out.print("De " + beginNode + " à " + i + " : ");
                pred = antecedant[i];

                String parcours = i + " - " + pred;

                while (pred != beginNode) {
                    pred = antecedant[pred];
                    parcours += " - " + pred;
                }
                StringBuilder strBuffer = new StringBuilder(parcours);
                parcours = strBuffer.reverse().toString();
                System.out.println("[ " + parcours + " ]");

                System.out.println(" Le cout de ce chemin est  " + distance[i]);
            }
        }
    }

    public Bellman(Graphe graphe) {
        this.graphe = graphe;
    }

    /**
     * Retourne une liste de plus court chemin en partant d'un sommet vers tout les autres sommets
     * @param beginNode Le sommet de depart
     */
    public void plusCourtChemin(int beginNode) {
        //  L'algorithme ne peut s'appliquer quand le graphe contient un circuit
        if (this.graphe.containsCircuit()) {
            System.out.println("Bellamn error : Le graphe contient un circuit");
            return;
        }
        //  Il ne faut pas que begin node ai un predecesseur
        if (UtilitaireAffichage.nbTrueValue(this.graphe.predecesseurs(beginNode)) > 0) {
            System.out.println("Bellamn error : Le sommet " + beginNode + " a un ou plusieurs predecesseur");
            return;
        }

        int INFINI = 1000000000;
        //  cout minimale
        int min;
        //  l'antecedant
        int sommetAntecedant;
        int ordre = this.graphe.getMatriceAdj().length;
        //  Le cout du chemin de beginNode au node autres sommet(indice du tableau)->correcpond au d(i) dans le sujet
        int[] distance = new int[ordre];
        //  Tableau contenant l'antecedant d'un sommet
        int[] antecedant = new int[ordre];
        //  La numerotaion topologique du graphe
        int[] numTopo = UtilitaireNumerotationTopologique.calulNumerotationTopographique(this.graphe);
        //  nombre de couche topologique
        int nbCoucheTopo = UtilitaireNumerotationTopologique.nbCoucheTopologique(numTopo);
        //  On initialise toute les distances à INFINI et ls antecedant à -1
        for (int i = 0; i < ordre; i++) {
            antecedant[i] = -1;
            distance[i] = INFINI;
        }

        //  la distance de beginNode à beginNode = 0 ce qui ets normal
        distance[beginNode] = 0;

        //  parcours des couhes topologique
        for (int couche = numTopo[beginNode] + 1; couche <= nbCoucheTopo; couche++) {

            //  parcours des sommets appartenant à cette couche
            for (int sommet = 0; sommet < ordre; sommet++) {
                min = INFINI;
                sommetAntecedant = -1;

                //  si le sommet appartient à cette couche
                if (numTopo[sommet] == couche) {
                    //  recup de tout les predecesseur de ce sommet
                    boolean[] predSommet = graphe.predecesseurs(sommet);
                    for (int pred = 0; pred < ordre; pred++) {
                        // si c'est un predecesseur
                        if (predSommet[pred] == true) {
                            int coutPredSommet = graphe.getMatriceAdjValue(pred, sommet);
                            if ((distance[pred] < INFINI)
                                    && (coutPredSommet + distance[pred] < min)) {
                                min = coutPredSommet + distance[pred];
                                sommetAntecedant = pred;
                            }
                        }   //  if
                    }   //  for
                    if (min < INFINI) {
                        distance[sommet] = min;
                        antecedant[sommet] = sommetAntecedant;

                    }   // if
                }   //  if
            }   //  for
        }   //  for
        //  Affichage
        this.displayResult(distance, antecedant, beginNode);
    }

    /**
     * Retourne une liste de plus court chemin en partant d'un sommet vers tout les autres sommets
     * @param beginNode Le sommet de depart
     */
    public void plusLongChemin(int beginNode) {
        //  L'algorithme ne peut s'appliquer quand le graphe contient un circuit
        if (this.graphe.containsCircuit()) {
            System.out.println("Bellamn error : Le graphe contient un circuit");
            return;
        }
        //  Il ne faut pas que begin node ai un predecesseur
        if (UtilitaireAffichage.nbTrueValue(this.graphe.predecesseurs(beginNode)) > 0) {
            System.out.println("Bellamn error : Le sommet " + beginNode + " a un ou plusieurs predecesseur");
            return;
        }

        int MOIN_INFINI = -1000000000;
        //  cout maximale
        int max;
        //  l'antecedant
        int sommetAntecedant;
        int ordre = this.graphe.getMatriceAdj().length;
        //  Le cout du chemax de beginNode au node autres sommet(indice du tableau)->correcpond au d(i) dans le sujet
        int[] distance = new int[ordre];
        //  Tableau contenant l'antecedant d'un sommet
        int[] antecedant = new int[ordre];
        //  La numerotaion topologique du graphe
        int[] numTopo = UtilitaireNumerotationTopologique.calulNumerotationTopographique(this.graphe);
        //  nombre de couche topologique
        int nbCoucheTopo = UtilitaireNumerotationTopologique.nbCoucheTopologique(numTopo);
        //  On initialise toute les distances à MOIN_INFINI et ls antecedant à -1
        for (int i = 0; i < ordre; i++) {
            antecedant[i] = -1;
            distance[i] = MOIN_INFINI;
        }

        //  la distance de beginNode à beginNode = 0 ce qui ets normal
        distance[beginNode] = 0;

        //  parcours des couhes topologique
        for (int couche = numTopo[beginNode] + 1; couche <= nbCoucheTopo; couche++) {

            //  parcours des sommets appartenant à cette couche
            for (int sommet = 0; sommet < ordre; sommet++) {
                max = MOIN_INFINI;
                sommetAntecedant = -1;

                //  si le sommet appartient à cette couche
                if (numTopo[sommet] == couche) {
                    //  recup de tout les predecesseur de ce sommet
                    boolean[] predSommet = graphe.predecesseurs(sommet);
                    for (int pred = 0; pred < ordre; pred++) {
                        // si c'est un predecesseur
                        if (predSommet[pred] == true) {
                            int coutPredSommet = graphe.getMatriceAdjValue(pred, sommet);
                            if ((distance[pred] > MOIN_INFINI)
                                    && (coutPredSommet + distance[pred] > max)) {
                                max = coutPredSommet + distance[pred];
                                sommetAntecedant = pred;
                            }
                        }   //  if
                    }   //  for
                    if (max > MOIN_INFINI) {
                        distance[sommet] = max;
                        antecedant[sommet] = sommetAntecedant;

                    }   // if
                }   //  if
            }   //  for
        }   //  for
        //  Affichage
        this.displayResult(distance, antecedant, beginNode);
    }
}
